public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */

    /*注意一下与最长公共子序列的区别*/
    public String LCS (String str1, String str2) {
        // write code here
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1+1][len2+1];
        int end =0;
        int maxNum = 0;

        for (int i = 1; i <= len1; ++i) {
            for (int j = 1; j <= len2; ++j) {
                if (str1.charAt(i-1) == str2.charAt(j-1)) {
                    dp[i][j] =dp[i-1][j-1] + 1;

                }
                if (dp[i][j] > maxNum) {
                    end = i-1;
                    maxNum = dp[i][j];
                }
            }
        }
        return str1.substring(end-maxNum+1,end+1);

    }
}
